home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Tools / Languages / Caml Light 0.61 / Source / src / lib / map.mli < prev    next >
Encoding:
Text File  |  1993-09-24  |  2.3 KB  |  45 lines  |  [TEXT/MPS ]
  1. (* Association tables over ordered types *)
  2.  
  3. (* This module implements applicative association tables, also known as
  4.    finite maps or dictionaries, given a total ordering function
  5.    over the keys.
  6.    All operations over maps are purely applicative (no side-effects).
  7.    The implementation uses balanced binary trees, and therefore searching
  8.    and insertion take time logarithmic in the size of the map. *)
  9.  
  10. type ('a, 'b) t;;
  11.         (* The type of maps from type ['a] to type ['b]. *)
  12.  
  13. value empty: ('a -> 'a -> int) -> ('a, 'b) t
  14.         (* The empty map.
  15.            The argument is a total ordering function over the set elements.
  16.            This is a two-argument function [f] such that
  17.            [f e1 e2] is zero if the elements [e1] and [e2] are equal,
  18.            [f e1 e2] is strictly negative if [e1] is smaller than [e2],
  19.            and [f e1 e2] is strictly positive if [e1] is greater than [e2].
  20.            Examples: a suitable ordering function for type [int]
  21.            is [prefix -]. For type [string], you could use
  22.            [compare_strings]. *)
  23.   and add: 'a -> 'b -> ('a, 'b) t -> ('a, 'b) t
  24.         (* [add x y m] returns a map containing the same bindings as
  25.            [m], plus a binding of [x] to [y]. Previous bindings for [x] 
  26.            in [m] are not removed, but simply hidden: they reappear
  27.            after performing a [remove] operation.
  28.            (This is the semantics of association lists.) *)
  29.   and find:'a -> ('a, 'b) t -> 'b
  30.         (* [find x m] returns the current binding of [x] in [m],
  31.            or raises [Not_found] if no such binding exists. *)
  32.   and remove: 'a -> ('a, 'b) t -> ('a, 'b) t
  33.         (* [remove x m] returns a map containing the same bindings
  34.            as [m] except the current binding for [x]. The previous
  35.            binding for [x] is restored if it exists. [m] is returned
  36.            unchanged if [x] is not bound in [m]. *)
  37.   and iter: ('a -> 'b -> 'c) -> ('a, 'b) t -> unit
  38.         (* [iter f m] applies [f] to all bindings in map [m],
  39.        discarding the results.
  40.            [f] receives the key as first argument, and the associated value
  41.            as second argument. The order in which the bindings are passed to
  42.            [f] is unspecified. Only current bindings are presented to [f]:
  43.            bindings hidden by more recent bindings are not passed to [f]. *)
  44. ;;
  45.